CPE 332
Computer Engineering
Mathematics II
Week 11
Part III, Chapter 9
Roots of Equations
• Roots of Equation
• Bracketing Method
– Bisection Method
– False Position Method
• Open Method
– Simple One-Point Iteration
– Newton-Ralphson Method
– Secant Method
– Multiple Roots Problem
– Modified Method
Roots of Equations
• กําหนด Function y=f(x)
– Zeroes ของ Function คือค่าของ x ที่ทําให ้
f(x)=0 หรือค่า y=0
– คือราก(root) ของสมการ f(x)=0 นั่นเอง
• ตัวอย่าง y=x3-2x2+x-5
– สมการ Polynomial, degree = 3
– ถ ้าเกิน Quadratic (Degree = 2) การหาราก
จะทําได ้ยาก, ไม่มีวิธีทาง Analytic Method โดยตรง เหมือน y=Ax2+Bx+C=0
2
− b ± b − 4 ac x =
2 a
• ตัวอย่าง y=x3-2x2+x-5
– วิธีทาง Numerical ที่เราเคยเรียนมาในวิชา
เรขาคณิตย์ คือ Plot Graph และหารากของ
สมการจาก Graph
• 1. แต่วิธีนี้จะให ้ค่าที่หยาบ
• 2. กรณีที่เป็น Complex Root จะหาไม่ได ้ จาก
Graph
Zeroes of Functions
y=x3-2x2+x-5
2.4
Zeroes of Functions
y=x3-2x2+x-5
4334
.
2
x = − 2167
.
+ j 417
.
1
− 2167
.
− j 417
.
1
2.4
• วิธีที่จะกล่าวต่อไป
– Numerical Method = Algorithm
– หา Zero Crossing (รากที่เป็นค่าจริง)
– สามารถได ้คําตอบให ้ถูกต ้องด ้วย Significant Digit มากเท่าที่เราต ้องการ
• ต ้อง Run Algorithm นานขึ้น
• Algorithm จะต ้อง Converge
– เป็น Iterative Method
• ถ ้า Algorithm Converge, แต่ละ Iteration ที่
Run จะให ้คําตอบที่ถูกต ้องขึ้นเรื่อยๆ
• จะช ้าหรือเร็วขึ้นอยู่กับ Convergence Rate ของแต่
ละ Algorithm
Methods
• Bracketing Method
– Bisection
– False Position
• Open Method
– Simple one-point Iteration
– Newton-Ralphson
– Secant Method
• ใช ้หลักความจริงที่ว่า เมื่อ f(x)=0 มันจะต ้อง
เปลี่ยนเครื่องหมาย
– ดังนั้น f(x-)f(x+) < 0 เมื่อ f(x)=0
• เราเริ่มจาก สองค่าของ x คือ xl และ xu ที่มี
คุณสมบัติ f(xl)f(xu) < 0
– อย่างน ้อยต ้องมีคําตอบหนึ่งอยู่ในช่วงนี้
• Algorithm จะ Search หาคําตอบในช่วง
Bracket นี้ โดยจะลดขนาดของ Bracket ลง
เรื่อยๆ
Bracketing Method
f ( x ) f ( x ) < 0
l
u
( x , f ( x )) u
u
xl
xu
( x , f ( x )) l
l
Bracketing Method
f ( x ) f ( x ) = 81
− < 0
l
u
(
)
9
,
7
x = 4
l
x = 7
u
( ,
4 − )
9
Bracketing Method:Bisection
Bracketing Method
x = (4 + 7) / 2 = 5.5
r
(
)
9
,
7
x = 4
l
x = 7
u
( ,
4 9
− )
Bracketing Method
x = (4 + 7) / 2 = 5.5
r
(
)
9
,
7
x = 4
x = 7
l
u
( x , f ( x )) r
r
.
5
(
,
5 − .
2
)
25
( ,
4 9
− )
xu=xr
Bracketing Method
(
)
9
,
7
x = 7
u
x = x =
5
.
5
l
r
Bracketing Method
(
)
9
,
7
x = 7
u
x = x =
5
.
5
l
r
x =
5
.
5
(
+ 7) / 2 = 25
.
6
r
Bracketing Method
x = x =
5
.
5
x = x
l
r
u
r
x =
5
.
5
(
+ 7) / 2 = 25
.
6
r
Bracketing Method:Bisection
Bracketing Method:Bisection
Bracketing Method:Bisection
.
667 38
f ( c) =
1
(
10
− c /
1
.
68
− e
) − 40 = 0
c
f
)
12
(
= 0669
.
6
38
.
667
f ( c) =
1
(
10
− c /
1
.
68
− e
) − 40 = 0
c
xu
x
x
l
r
f
)
16
(
= 2
− 2688
.
x = 12
(
+ )
16 / 2 = 14
r
f x
=
f
)
14
(
= 5687
.
1
(
)
1 5687
.
r
(2)
f
)
12
(
= 0669
.
6
x
= x = 14
u
r
38
.
667
f ( c) =
1
(
10
− c /
1
.
68
− e
) − 40 = 0
c
xu
x
x
l
r
f
)
16
(
= 2
− 2688
.
x = 12
(
+ )
16 / 2 = 14
r
f
)
14
(
= 5687
.
1
x = 14
(
+ )
16 / 2 = 15
38
.
667
r
f ( c) =
1
(
10
− c /
1
.
68
− e
) − 40 = 0
c
x
x
r
u
xl
f
)
16
(
= 2
− 2688
.
Bracketing Method: Bisection
False-Position Method
False-Position Method
False-Position Method
False-Position Method
False-Position Method
False-Position Method
Open Method:
Simple One-Point Iteration
Open Method:
Simple One-Point Iteration
Open Method:
Simple One-Point Iteration
Open Method:
Simple One-Point Iteration
Open Method:
Simple One-Point Iteration
Open Method:
Newton-Ralphson Method
Open Method:
Newton-Ralphson Method
Open Method:
Newton-Ralphson Method
Open Method:
Newton-Ralphson Method
Open Method:
Newton-Ralphson Method
Open Method:
Secant Method
Open Method:
Secant Method
Open Method:
Secant Method
Multiple Roots
Multiple Roots
Multiple Roots
Multiple Roots
Multiple Roots
Multiple Roots
Multiple Roots
Comparison
Comparison
Comparison
• นักศึกษาต ้องเขียนโปรแกรมช่วยคํานวณ
หรือใช ้ Spreadsheet (MS Excel) ช่วย
คํานวณ
– แนะนําให ้ใช ้ MATLAB
• เขียน Function หรือ Scratch File ก็ได ้
• หรือคํานวณจาก Workspace โดยตรง
• Download คําถามและตอบคําถาม